
public class Avl<T extends Comparable<T>> {

    public Node root;

    public Avl() {
        this.root = new Node();
    }

    public void insert(T new_data) {
        insertAVL(root, null, false, new_data);
    }

    public void remove(T old_data) {
        removeAVL(root, null, false, old_data);
    }

    public T getSuccessor(T data) {
        return getAVLSuccessor(root, data);
    }

    public T getPredecessor(T data) {
        return getAVLPredecessor(root, data);
    }

    protected void insertAVL(Node node, Node father, boolean left, T new_data) {
        if (node.isEmpty()) {
            node.data = new_data;
            node.left = new Node();
            node.right = new Node();
        } else if (node.data.compareTo(new_data) > 0) {
            insertAVL(node.right, node, false, new_data);
            equilibrate(node, father, left);
        } else if (node.data.compareTo(new_data) < 0) {
            insertAVL(node.left, node, true, new_data);
            equilibrate(node, father, left);
        }
    }

    protected void removeAVL(Node node, Node father, boolean left, T old_data) {
        if (!node.isEmpty()) {
            if (node.data.compareTo(old_data) < 0) {
                removeAVL(node.left, node, true, old_data);
                equilibrate(node, father, left);
            } else if (node.data.compareTo(old_data) > 0) {
                removeAVL(node.right, node, false, old_data);
                equilibrate(node, father, left);
            } else {
                removeRootAVL(node, father, left);
            }
        }
    }

    protected void removeRootAVL(Node node, Node father, boolean left) {
        if (node.isLeaf()) {
            if (left && father != null) {
                father.left = new Node();
            } else if(!left && father != null) {
                father.right = new Node();
            } else {
                root = new Node();
            }
        } else if (node.left.isEmpty()) {
            if (left && father != null) {
                father.left = node.right;
            } else if(!left && father != null) {
                father.right = node.right;
            } else {
                root = node.right;
            }
        } else if (node.right.isEmpty()) {
            if (left && father != null) {
                father.left = node.left;
            } else if(!left && father != null) {
                father.right = node.left;
            } else {
                root = node.left;
            }
        } else {
            node.data = removeMinAVL(node.right, node, false);
            equilibrate(node, father, left);
        }
    }

    protected T removeMinAVL(Node node, Node father, boolean left) {
        T min;
        if (node.left.isEmpty()) {
            min = (T) node.data;
            if (left) {
                father.left = node.right;
            } else {
                father.right = node.right;
            }
        } else {
            min = removeMinAVL(node.left, node, true);
            equilibrate(node, father, left);
        }
        return min;
    }

    protected void leftRotation(Node node, Node father, boolean left) {
        Node temp = node;
        node = node.right;
        temp.right = node.left;
        node.left = temp;
        if (father == null) {
            root = node;
        } else if (left) {
            father.left = node;
        } else {
            father.right = node;
        }
        temp.height();
        node.height();
    }

    protected void rightRotation(Node node, Node father, boolean left) {
        //System.out.println(node.equals(root));
        Node temp = node;
        node = node.left;
        temp.left = node.right;
        node.right = temp;
        if (father == null) {
            root = node;
        } else if (left) {
            father.left = node;
        } else {
            father.right = node;
        }
        temp.height();
        node.height();
    }

    protected void equilibrate(Node node, Node father, boolean left) {
        if (node.bal() == 2) {
            if (node.right.bal() >= 0) {
                leftRotation(node, father, left);
            } else {
                rightRotation(node.right, node, false);
                leftRotation(node, father, left);
            }
        } else if (node.bal() == -2) {
            if (node.left.bal() <= 0) {
                rightRotation(node, father, left);
            } else {
                leftRotation(node.left, node, true);
                rightRotation(node, father, left);
            }
        } else {
            node.height();
        }
    }

    protected T getAVLSuccessor(Node node, T data) {
        if (node.data.compareTo(data) >= 0) {
            if (!node.right.isEmpty()) {
                return getAVLSuccessor(node.right, data);
            } else {
                return null;
            }
        } else {
            if (!node.left.isEmpty()) {
                T result = getAVLSuccessor(node.left, data);
                if (result != null) {
                    return result;
                }
            }
            return (T) node.data;
        }
    }

    protected T getAVLPredecessor(Node node, T data) {
        if (node.data.compareTo(data) <= 0) {
            if (!node.left.isEmpty()) {
                return getAVLPredecessor(node.left, data);
            } else {
                return null;
            }
        } else {
            if (!node.right.isEmpty()) {
                T result = getAVLPredecessor(node.right, data);
                if (result != null) {
                    return result;
                }
            }
            return (T) node.data;
        }
    }

    protected T getFirstNode(Node node, Node father, boolean left) {
        if(node.isEmpty()) return null;
        if (node.isLeaf()) {
            /*if (father != null && left) {
                father.left = new Node();
            } else if (father != null) {
                father.right = new Node();
            }/* Suppression à décider */
            return (T) node.data;
        } else if (!node.left.isEmpty()) {
            return getFirstNode(node.left, node, true);
        } else if (!node.right.isEmpty()) {
            return getFirstNode(node.right, node, false);
        }
        return null; //En cas d'erreur - ne doit jamais y parvenir si tout va bien
    }
}
